package com.example.binarytree;

/**
 * @author Jonathan
 * 2021/4/15 21:28
 * <p>
 * 这个为什么也不对？
 */
public class DiameterOfBinaryTree {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public static class Info {
        public int maxDistance;
        public int height;

        public Info(int maxDistance, int height) {
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }

    public int diameterOfBinaryTree(TreeNode root) {
        return process(root).maxDistance;

    }

    public Info process(TreeNode x) {
        if (x == null) {
            return new Info(0, 0);
        }
        Info left = process(x.left);
        Info right = process(x.right);
        int height = Math.max(left.height, right.height) + 1;
        // 主要是看是不是经过当前节点
        int maxDistance = Math.max(Math.max(left.maxDistance, right.maxDistance), left.height + right.height + 1);
        return new Info(maxDistance, height);
    }
}
